package com.xk._02算法篇._05backTracking;

import com.xk.tools.Times;

/**
 * @description: N皇后问题 -- 优化1
 * @author: xu
 * @date: 2022/10/16 20:06
 */
public class NQueens1 {
    public static void main(String[] args) {
        Times.test("testNQueen1", () -> new NQueens1().plateQueens(12));
    }

    /**
     * 数组索引是行号，数组列数是列号
     */
    int[] queens;
    /**
     * 标记着某一列是否有皇后了
     */
    boolean[] cols;
    /**
     * 标记着某一对角线是否有皇后了（左上角 --> 右下角  left top --> right bottom）
     */
    boolean[] leftTop;
    /**
     * 标记着某一对角线是否有皇后了（右上角 --> 左下角  right top --> left bottom）
     */
    boolean[] rightTop;
    /**
     * 一共有多少种合理的摆法
     */
    int ways;

    void plateQueens(int num) {
        if (num < 1) return;
        queens = new int[num];
        cols = new boolean[num];
        leftTop = new boolean[(num << 1) - 1];
        rightTop = new boolean[leftTop.length];
        place(0);
        System.out.println(num + "皇后一共有" + ways + "种摆法");
    }

    /**
     * 从第 row 行开始摆放皇后
     * @param row
     */
    void place(int row){
        if (row == cols.length) {
            ways++;
            show();
            return;
        }
        for (int col = 0; col < cols.length; col++) {
            // 剪枝处理
            if (cols[col]) continue;
            int ltIndex = row - col + cols.length - 1;
            int rtIndex = row + col;
            if (leftTop[ltIndex] || rightTop[rtIndex]) continue;

            // 在第row行，第col列摆放皇后
            cols[col] = true;
            leftTop[ltIndex] = true;
            rightTop[rtIndex] = true;
            queens[row] = col;
            place(row + 1);

            // 状态重置
            cols[col] = false;
            leftTop[ltIndex] = false;
            rightTop[rtIndex] = false;
        }
    }

    void show(){
        for (int row = 0; row < queens.length; row++) {
            for (int col = 0; col < queens.length; col++) {
                if (queens[row] == col) {
                    System.out.print("1 ");
                } else {
                    System.out.print("0 ");
                }
            }
            System.out.println();
        }
        System.out.println("=====================");
    }
}
